import java.util.Arrays;
import java.util.Random;

public class text {
    public static void Insert_Sort(int[] array) {
        for (int j = 1; j < array.length; j++) { //从数组的第二个数字开始迭代

            int i = j - 1;  // i 的更新 ，保证在留空时不会被改成无效变量
            int key = array[j];  // key 每次要操作的值

            while (i >= 0 && array[i] > key) {  //i >= 0，保证留空能检查到第一位  array[i] > key ：交换的条件
                array[i + 1] = array[i];  //留空
                i--;
            }
            array[i + 1] = key;  //赋值
        }
    }


    public static void Insert_Sort1(int[] array) {
        for (int j = 1; j < array.length; j++) {
            int i = j - 1;
            int key = array[j];

            while (i >= 0 && array[i] > key) {
                array[i + 1] = array[i];
                i--;
            }
            array[i + 1] = key;
        }
    }


    public static void main(String[] args) {
        long start = System.currentTimeMillis();


        int[] array = new int[100000];




        int key;

        for (int i = 0; i < 100000; i++) {
            Random random = new Random();
            array[i] = random.nextInt();
        }
        Insert_Sort(array);
        System.out.println(Arrays.toString(array));

        long end = System.currentTimeMillis();
        long runtime = start - end;
        System.out.println("程序运行的时间为：" + runtime + "毫秒级");
    }
}

